package com.kehao.leetcode.middle.tree_graph;

import org.junit.Test;

import java.util.HashMap;

public class PrefectBiTreeConnectSolution {
    private class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    public Node connect(Node root) {
        if(root==null) return root;
        if(root.left!=null){
            root.left.next = root.right;//节点下面的左右节点相连
            if(root.left.left!=null){
                Node left = root.left.right;
                Node right = root.right.left;
                while (left!=null){
                    left.next = right;
                    left = left.right;
                    right = right.left;
                }
                connect(root.left);
                connect(root.right);
            }
        }
        return root;
    }

    @Test
    public void test01(){
        int[] array = {1,2,3,4,5,6,7};
        Node root = buildTree(array);
        connect(root);
        while (root!=null){
            Node p = root;
            while (p!=null){
                System.out.print(p.val+" ");
                p=p.next;
            }
            System.out.println("#");
            root = root.left;
        }
    }

    @Test
    public void test02(){
        int[] array = {-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13};
        Node root = buildTree(array);
        connect(root);
        while (root!=null){
            Node p = root;
            while (p!=null){
                System.out.print(p.val+" ");
                p=p.next;
            }
            System.out.println("#");
            root = root.left;
        }
    }

    private Node buildTree(int[] array) {
        HashMap<Integer,Node> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            map.put(i,new Node(array[i]));
        }
        for (int i = 0; i < array.length; i++) {
            map.get(i).left = map.get(i*2+1);
            map.get(i).right = map.get(i*2+2);
        }
        return  map.get(0);
    }


}
